/*
题目：求众数Ⅱ
给定一个大小为 n 的整数数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。
 */
public class MajorityElement {
    public List<Integer> majorityElement(int[] nums) {
        List<Integer> ans = new ArrayList<>();
        int vote1 = 0;
        int vote2 = 0;
        int ele1 = 0;
        int ele2 = 0;
        for (int x : nums) {
            //必须要先判断和ele1和ele2相不相等，否则本来是自己的位置有可能被占
            if (vote1 > 0 && ele1 == x) {
                vote1 ++;
            } else if (vote2 > 0 && ele2 == x) {
                vote2++;
            } else if (vote1 == 0) {
                vote1++;
                ele1 = x;
            } else if (vote2 == 0) {
                vote2++;
                ele2 = x;
            } else {
                vote1--;
                vote2--;
            }
        }
        vote1 = vote2 = 0;
        for (int x : nums) {
            if (ele1 == x) {
                vote1++;
            } else if (ele2 == x) {
                vote2++;
            }
        }
        if (vote1 > nums.length / 3) {
            ans.add(ele1);
        }
        if (vote2 > nums.length / 3) {
            ans.add(ele2);
        }
        return ans;
    }
}
